package com.wj.algorithm.lintcode;

import java.util.HashMap;
import java.util.Map;

import com.wj.algorithm.ArrayUtil;

public class P548 {
    
    public Map<Integer, Integer> createMap(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i : nums) {
            Integer count = map.get(i);
            if(count == null) {
                map.put(i, 1);
            } else {
                map.put(i, count + 1);
            }
        }
        return map;
    }
    
    public int[] intersection(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        if(len1 == 0 || len2 == 0) {
            return new int[0];
        }
        
        Map<Integer, Integer> map1 = createMap(nums1);
        
        Map<Integer, Integer> temp = new HashMap<Integer, Integer>();
        int total = 0;
        for(int i : nums2) {
            Integer count1 = map1.get(i);
            if(count1 == null) {
                continue;
            }
            Integer count = temp.get(i);
            if(count == null) {
                temp.put(i, 1);
                total ++;
            } else if(count < count1) {
                temp.put(i, count + 1);
                total ++;
            }
        }
        

        int[] rs = new int[total];
        int index = 0;
        for(Map.Entry<Integer, Integer> en : temp.entrySet()) {
            int v = en.getValue();
            int i = en.getKey();
            int j = 0;
            while(j < v) {
                rs[index] = i;
                j ++;
                index ++;
            }
        }
        
        return rs;
    }
    
    public static void main(String[] args) {
        int[] a = new int[]{1,2,2,1};
        int[] b = new int[]{2,2};
        
        int[] rs = new P548().intersection(a, b);
        System.out.println(ArrayUtil.toString(rs));
    }
}
